package com.localking.algorithm.leetcode.array

/**
 * Given an array of n positive and a positive integer s, find the minimal length of a contiguous subarray of which the sum >= s. If there isn't one ,return 0 instead.
 *
 * Example:
 * Input: s = 7, nums = [2, 3, 1, 2, 4, 3]
 * Output: 2
 * Explanation: the subarray [4, 3] has the minimal length under the problem constraint.
 *
 * Follow up:
 * If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
 *
 * @author jinbo
 */
object MinSubArrayLen {
  def main(args: Array[String]): Unit = {
    val s = 4
    val nums = Array(1, 4, 4)
    println(minSubArrayLen(s, nums))
  }

  def minSubArrayLen(s: Int, nums: Array[Int]): Int = {
    var min = 0
    var start = 0
    var sum = 0
    for(i <- nums.indices) {
      sum += nums(i)
      while (sum >= s && start <= i) {
        val currentLen = i - start + 1
        if(min == 0 || currentLen < min) {
          min = currentLen
        }
        sum -= nums(start)
        start += 1
      }
    }
    min
  }
}
